from typing import List

class Solution:
    def dailyTemperatures(self, T: List[int]) -> List[int]:
        lps = [0] * 101 # lps[i] 表示温度 i 从后往前数最后一次，注意 lps[i] 的值是变化的
        size = len(T)
        result = [0] * size
        for j in range(size):
            i = size - j - 1
            t = T[i]
            lgi = self.findLatestGreaterTemperatureIndex(lps, t)
            result[i] = lgi - i if lgi < 1000000 else 0
            lps[t] = i
        return result

    def findLatestGreaterTemperatureIndex(self, lps, t):
        i = t + 1
        size = len(lps)
        result = 1000000
        while i < size:
            if lps[i] > 0:
                result = min(result, lps[i])
            i += 1
        return result

solu = Solution()
print(solu.dailyTemperatures([73, 74, 75, 71, 69, 72, 76, 73]))